10324. Нули и единицы

Дана последовательность из 0 и 1 длины 1000000. По заданным позициям i и j определить, будут ли все символы между позициями min(i, j) и max(i, j) включительно одинаковыми.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит последовательность нулей и единиц. Следующая строка содержит количество запросов. Каждый запрос состоит из двух неотрицательных чисел i и j.

Выход. Для каждого теста вывести его номер, для каждого запроса (i, j) вывести “Yes” или “No” в зависимости от того, будут ли все символы между позициями min(i, j) и max(i, j) включительно одинаковыми.

Пример входа

0000011111
3
0 5
4 2
5 9
01010101010101010101010101111111111111111111111111111111111110000000000000000
5
4 4
25 60
1 3
62 76
24 62
1
1
0 0

Пример выхода

Case 1:
No
Yes
Yes
Case 2:
Yes
Yes
No
Yes
No
Case 3:
Yes

РЕШЕНИЕ

обработка массива

Анализ алгоритма

Заведем массив m на 1000000 целых чисел и заполним его следующим образом:

m[0] = 0,

m[i] = m[i – 1], если i - ый элемент равен (i – 1) - ому,

m[i] = m[i – 1] + 1, если i - ый элемент не равен (i – 1) - ому.

Тогда для любых индексов i и j (i < j или i > j) m[i] = m[j] тогда и только тогда, когда все элементы последовательности от i – го до j – го равны. Запрос (i, j) к последовательности будет выполняться за константное время.

Пример

Первый тест состоит из строки длины 10, номера позиций изменяются от 0 до 9. На позициях с 0 до 4 стоят нули, на позициях с 5 до 9 стоят единицы. Для первого запроса i = 0, j = 5 ответ No, так как на 4 и 5 позициях стоят разные числа. Для второго и третьего запросов ответы Yes, так как на позициях с 2 по 4 стоят только нули, а с 5 по 9 стоят только единицы.

Реализация алгоритма

В переменной cs будем хранить номер теста, в переменной s входную последовательность, в переменной len – ее длину.

#define MAX 1000000

int m[MAX];

char s[MAX];

int cs, i, j, k, n, len;

Заполним элементы массива m числами согласно выше описанному правилу. Изначально положим m[0] = 0.

cs = 1;

while(scanf("%s",s) == 1)

{

m[0] = 0;

printf("Case %d:\n",cs++);

len = (int)strlen(s);

for(i = 1; i < len; i++)

{

m[i] = m[i-1];

if (s[i] != s[i-1]) m[i]++;

}

Читаем число запросов n. Для каждого запроса (i, j) выводим “Yes”, если m[i] = m[j] и “No” в противном случае.

scanf("%d",&n);

for(k = 0; k < n; k++)

{

scanf("%d %d",&i,&j);

if (m[i] == m[j]) printf("Yes\n"); else printf("No\n");

}

}